package q871_minRefuelStops;

public class Solution_1 {
    /*
    动态规划
     */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        // 用dp[i] 表示加油 i 次的最大行驶英里数
        long[] dp = new long[n + 1];
        // 加0次油能跑的里数显然就是初试的油数
        dp[0] = startFuel;
        for (int i = 0; i < n; i++) {
             /*
             详细解释一下为啥更新最大的一次加油，一定得让j从i--到0去更新，而不是从0++到i更新
             以示例 3 为例: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
             dp[0]=10,dp[0]>=stations[0][0] -->dp[1]=10+60=70，(第一次油加60的这桶)
             对于加油站 stations[2] 计算之后dp[2] = 70+30=100。(第二次加30的这桶)

             如果j从小到大更新:
             对于加油站 stations[3] 计算的过程中会将dp[2] 的值更新为 110，(先将第二次加的油从30改成加40那桶)
             使得更新完dp[2] 了之后才来更新dp[3]，
             dp[3] 的值将被错误地计算为 dp[2]+stations[3][1]=110+40=150。(第二桶加了40那桶，第三桶也加了40那桶，加了两次40的油)

             所以只有当从大到小遍历下标 j 时，才能得到 dp[3]=140 的正确结果
             */
            for (int j = i; j >=0 ; j--) {
                // 若当前能到达下一个加油站，拿下一个加油站能加的这桶油，去更新上一次加的一桶油，一桶一桶直至达到每一桶最大
                if (dp[j] >= stations[i][0]) {
                    // 把前面的每一桶油更新成最大的那桶，如当能到达第三个加油站时,他能做到更新前面加了2桶的，和加一桶的
                    // 加3桶能跑的数 = max ( <前面已经加的3桶能跑的数(还未更新,dp[3]还是0)> , <前面加了2桶,第3桶换成此桶油能跑的数> )
                    // 加2桶能跑的数(更新) = max ( <前面已经加的2桶能跑的数> , <前面加了1桶，第2桶换成此桶油能跑的数> )
                    // 加1桶能跑的数(更新) = max ( <前面已经加的1桶能跑的数> , <前面加了0桶，第1桶换成此桶油能跑的数> )

                    dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            if (dp[i] >= target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        int target = 100;
        int start = 1;
        int[][] stations = {};
        System.out.println(s.minRefuelStops(target, start, stations));
    }
}
